1. Field of the Invention
The present invention relates to computer networks and more particularly to Fast Convergence for non-multipath Border Gateway Protocol (BGP) paths in a computer network.
2. Background Information
A computer network is a geographically distributed collection of nodes interconnected by communication links and segments for transporting data between end nodes, such as personal computers and workstations. Many types of networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect the nodes over dedicated private communications links located in the same general physical location, such as a building or campus. WANs, on the other hand, typically connect geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines, optical lightpaths, synchronous optical networks (SONET), or synchronous digital hierarchy (SDH) links. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol consists of a set of rules defining how the nodes interact with each other. Computer networks may be further interconnected by an intermediate network node, such as a router, to extend the effective “size” of each network.
Since management of interconnected computer networks can prove burdensome, smaller groups of computer networks may be maintained as routing domains or autonomous systems. The networks within an autonomous system (AS) are typically coupled together by conventional “intradomain” routers configured to execute intradomain routing protocols, and are generally subject to a common authority. To improve routing scalability, a service provider (e.g., an ISP) may divide an AS into multiple “areas.” It may be desirable, however, to increase the number of nodes capable of exchanging data; in this case, interdomain routers executing interdomain routing protocols are used to interconnect nodes of the various ASes. Moreover, it may be desirable to interconnect various ASes that operate under different administrative domains. As used herein, an AS is generally referred to as a “domain,” and a router that interconnects different domains is generally referred to as a “border router.”
An example of an interdomain routing protocol is the Border Gateway Protocol version 4 (BGP), which performs routing between domains (ASes) by exchanging routing and reachability information among neighboring interdomain routers of the systems. An adjacency is a relationship formed between selected neighboring (peer) routers for the purpose of exchanging routing information messages and abstracting the network topology. The routing information exchanged by BGP peer routers (BGP speakers or BGP nodes) typically includes destination address prefixes, i.e., the portions of destination addresses used by the routing protocol to render routing (“next hop”) decisions. Examples of such destination addresses include IP version 4 (IPv4) and version 6 (IPv6) addresses. BGP generally operates over a reliable transport protocol, such as TCP, to establish a TCP connection/session. The BGP protocol is well known and generally described in Request for Comments (RFC) 1771, entitled A Border Gateway Protocol 4 (BGP-4), published March 1995, the contents of which are hereby incorporated in its entirety.
An intermediate network node often stores its routing information in a routing table maintained and managed by a routing information base (RIB). The routing table is a searchable data structure in which network addresses are mapped to their associated routing information. However, those skilled in the art will understand that the routing table need not be organized as a table, and alternatively may be another type of searchable data structure. Although the intermediate network node's routing table may be configured with a predetermined set of routing information, the node also may dynamically acquire (“learn”) network routing information as it sends and receives data packets. When a packet is received at the intermediate network node, the packet's destination address may be used to identify a routing table entry containing routing information associated with the received packet. Among other things, the packet's routing information indicates the packet's next-hop address.
To ensure that its routing table contains up-to-date interdomain routing information, the intermediate network node may cooperate with other intermediate nodes to disseminate routing information representative of the current network topology. Typically, routing information is disseminated among interconnected intermediate network BGP nodes through advertising BGP update messages, or “BGP advertisements.” As used herein, a BGP advertisement generally describes any message used by a BGP routing protocol for communicating routing information among interconnected BGP nodes, i.e., routers and switches. Operationally, a remote BGP node (e.g., of a remote domain) may establish a BGP session with a local BGP node (e.g., of a local domain), and transmit a generated BGP advertisement to the local BGP node. Thereafter, the local BGP node may receive the transmitted BGP advertisement and update its routing table based on routing information contained in the received BGP advertisement. Note that a BGP session between local and remote domains (interdomain) is an external BGP (eBGP) session. The local BGP node may then transmit the received BGP advertisement to other BGP nodes of the local domain until each interconnected BGP node of the local domain has received the BGP advertisement and updated its local routing table. Note further that a BGP session within a domain (intradomain) is an internal BGP (iBGP) session. BGP nodes within a domain, such as an AS, are typically connected via a fully meshed iBGP session arrangement to ensure that all BGP nodes receive advertisements from the other BGP nodes in the AS. Note still further that eBGP and iBGP are generally referred to herein as “BGP.” Moreover, a BGP session may be a multi-hop BGP session, such as where there are intermediate nodes/devices between the edge devices.
BGP route selection, as described herein, may utilize a distance vector (Bellman-Ford) algorithm or, more specifically, a BGP best path selection (path vector) algorithm, or a “best BGP path selection algorithm”. According to the BGP standard, every BGP router announces to all of its peers the routes it uses for its own forwarding. As a result of these announcements (i.e., BGP advertisements), a particular router may gather from its peers two or more routes for some networks. For example, the router may have learned two or more different ways to reach a particular destination prefix, and the best BGP path selection computation is a way of choosing one of those routes as “best” and using it to render forwarding decisions for the router (i.e., the best route is installed into the routing table).
Multipath BGP allows installation of multiple BGP paths for the same destination prefix into the routing table. These multiple BGP paths may be installed into the routing table along with the best BGP path to enable load sharing/balancing, as will be understood by those skilled in the art. In order to be candidates for multipath BGP selection, paths to the same destination prefix may be required to share a number of characteristics equal to the best BGP path, e.g., weight, local preference, AS-Path length, Origin, MED, etc., as will be also be understood by those skilled in the art. Note that in the case of multipath BGP, these multiple chosen paths are only installed into the local routing table, and only the best BGP path for each prefix may be advertised to BGP peers. Commonly, multipath BGP must be configured on the BGP node in order to be operational.
Occasionally, a network element (e.g., a node or link) fails, causing redirection of the traffic that originally traversed the failed network element to other network elements that bypass the failure. Generally, notice of this failure is relayed to the surrounding nodes in the network through one or more advertisements of the new network topology, e.g., IGP and/or BGP advertisements, and routing tables are updated to avoid the failure accordingly. Reconfiguring a network in response to a network element failure using, e.g., pure IP rerouting, can be time consuming. In the case of BGP paths, in particular, the network element failure may cause a failure of the best BGP path currently installed in the routing table of a particular BGP node (e.g., a border router). In this case, a substantial amount of BGP calculation must be performed for each reachable destination prefix previously utilizing the failed best BGP path in order to converge the routing table to the current network topology. The propagation/installation of the BGP information into the routing tables may also cause lengthy delay. These computations and delays may result in lost traffic or other adverse network conditions, as those skilled in the art will understand.
Many recovery techniques, however, are available to provide fast recovery and/or network configuration in the event of a network element failure, including, inter alia, Fast Reroute (FRR). FRR has may be deployed to protect against network element failures, where “backup tunnels” are created and set up a priori (before the occurrence of the failure) to bypass a protected network element (e.g., links, shared risk link groups (SRLGs), and nodes). When the network element fails, traffic is quickly rerouted over a backup tunnel to bypass the failed element. An example protocol that may advantageously use backup tunnels is the Multiprotocol Label Switching (MPLS) protocol, as will be understood by those skilled in the art.
Aside from backup tunnels (e.g., for networks not configured with tunneling protocols), various approaches have been suggested for reducing the BGP convergence time in case of failures. For instance, reducing the number of BGP messages exchanged after a failure may reduce the convergence time. An additional proposed technique is described in “Fast Scoped Rerouting for BGP,” International Conference on Networks, pages 25-30, IEEE, September 2003, which requires BGP routers to find an alternate path for a destination after a failure as a result of which recovery time is still long. Multipath BGP, however, allows for multiple BGP paths to be inserted into the routing table. In this instance, should one of the multipath BGP paths fail, other multipath BGP paths may be available to reach the destination prefix. As mentioned, however, multipath BGP paths may only exist when the multiple paths are equal in (share) a number of characteristic categories, and only on BGP nodes configured for multipath BGP.
There remains a need, therefore, for a technique that provides FRR (or “Fast Convergence”) to BGP paths in a computer network that substantially eliminates per-prefix convergence delay (e.g., BGP computation and/or routing table information propagation), without the use of backup tunnels or multipath BGP.